#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void MySort(vector<int> &num);

class Solution{
    public:
    //直接排序sort函数
    void merge1(vector<int>& num1, int m, vector<int>& num2, int n){
        for(int i = 0; i != n; i++){
            num1[m+i] = num2[i];
        }
        sort(num1.begin(), num1.end());
    }
    //直接排序自定义MySort函数
    void merge2(vector<int>& num1, int m, vector<int>& num2, int n){
        for(int i = 0; i != n; i++){
            num1[m+i] = num2[i];
        }
        MySort(num1);
    }
    //双指针-->耗时最少
    void merge3(vector<int>& num1, int m, vector<int>& num2, int n){
        int p1 = 0, p2 = 0;
        int sorted[m+n];
        int temp;
        while(p1 < m || p2 < n){
            if(p1 == m){
                temp = num2[p2];
                p2++;
            }
            else if(p2 == n){
                temp = num1[p1];
                p1++;
            }
            else if(num1[p1] < num2[p2]){
                temp = num1[p1];
                p1++;
            }
            else{
                temp = num2[p2];
                p2++;
            }
            sorted[p1+p2-1] = temp;
        }
        for(int i = 0; i != num1.size(); i++){
            num1[i] = sorted[i];
        }
    }
    //逆向双指针-->不会出现元素覆盖，因此不需要创建新数组
    void merge4(vector<int>& num1, int m, vector<int>& num2, int n){
        int p1 = m, p2 = n;
        int length = m+n-1;
        int temp;
        while(p1 > 0 || p2 > 0){
            if(p1 == 0){
                temp = num2[p2-1];
                p2--;
            }
            else if(p2 == 0){
                temp = num1[p1-1];
                p1--;
            }
            else if(num1[p1-1] > num2[p2-1]){
                temp = num1[p1-1];
                p1--;
            }
            else{
                temp = num2[p2-1];
                p2--;
            }
            num1[length] = temp;
            length--;
        }
    }

    void show(vector<int>& num1){
        int length = num1.size();
        for(int i = 0; i != length; i++){
            cout << num1[i] << " " << ends;
        }
        cout << endl;
    }

};

void MySort(vector<int> &num){
    int length = num.size();
    for(int i = 0; i < length-1; i++){
        for(int j = i+1; j < length; j++){
            if(num[i] > num[j]){
                int temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }
}

void test1(){
    vector<int> num1 = {1, 2, 3, 0, 0, 0};
    int m = 3;
    vector<int> num2 = {2, 5, 6};
    int n = 3;
    
    Solution s;
    //s.merge1(num1, m, num2, n);
    //s.merge2(num1, m, num2, n);
    //s.merge3(num1, m, num2, n);
    s.merge4(num1, m, num2, n);
    s.show(num1);
}

void test2(){
    vector<int> num1 = {1};
    int m = 1;
    vector<int> num2 = {};
    int n = 0;

    Solution s;
    //s.merge1(num1, m, num2, n);
    //s.merge2(num1, m, num2, n);
    //s.merge3(num1, m, num2, n);
    s.merge4(num1, m, num2, n);
    s.show(num1);
}

void test3(){
    vector<int> num1 = {0, 0};
    int m = 0;
    vector<int> num2 = {1, 2};
    int n = 2;

    Solution s;
    //s.merge1(num1, m, num2, n);
    //s.merge2(num1, m, num2, n);
    //s.merge3(num1, m, num2, n);
    s.merge4(num1, m, num2, n);
    s.show(num1);
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}